package com.gorkr.labuladong.data_struct.struct;

import java.util.LinkedHashMap;

/**
 * @author gorkr
 * @date 2022/06/13 11:29
 **/
public class M146LRUcache {

    // 容量
    private int capacity;

    // 哈希双向链表
    private LinkedHashMap<Integer, Integer> cache;


    public M146LRUcache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<>();
    }

    public int get(int key) {
        // 不存在
        if(!cache.containsKey(key)){
            return -1;
        }
        // 存在 取出 并放在最近使用
        Integer value = cache.get(key);
        makeRecent(key,value);
        return value;
    }


    // 这个必须了解hashmap的底层实现吧
    public void put(int key, int value) {
        // 如果存在 提成为最近使用
        if(cache.containsKey(key)){
            // 删除 再插入
            cache.remove(key);
            cache.put(key,value);
            return;
        }

        // 如果不存在
        // 超出容量置换出去
        if(cache.size()>=capacity){
            // 换出队头元素
            Integer oldest = cache.keySet().iterator().next();
            cache.remove(oldest);
        }
        // 队尾插入
        cache.put(key,value);

    }

    private void makeRecent(int key, int value){
        int val = cache.get(key);
        // 根据底层实现插入队尾？？？
        cache.remove(key);
        cache.put(key,value);
    }

}
    